package leetcode.day;

import java.math.BigInteger;

// 69. x 的平方根
public class MySqrt {

    public static void main(String[] args) {
        System.out.println(mySqrt2(2147395599));
    }

    // 超时且运行不出来大数
    public static int mySqrt(int x) {
        BigInteger res = new BigInteger("0");
        BigInteger i = new BigInteger("1");
        BigInteger m = new BigInteger(x + "");
        for (; i.compareTo(m) <= 0; ) {
            BigInteger n = i.multiply(i);
            if (n.compareTo(m) <= 0) {
                res = i;
            }
            i = i.add(new BigInteger("1"));
        }
        return res.intValue();
    }

    // 二分
    public static int mySqrt2(int x) {
        if (x == 1) {
            return 1;
        }
        int left = 1;
        int right = x;
        while (left < right) {
            int mid = left + (right - left) / 2;
            // 这里并不能直接比较 mid*mid < x， 原因是 signed integer 大小会溢出，
            // 所以应该是 mid < x/mid
            if (mid < x / mid) {
                left = mid+1;
            } else {
                right = mid;
            }
        }
        return left == x / left ? left : left - 1;
    }
}
